﻿using System;

namespace SpatialHashLib.Topology
{
    public struct Segment : IEquatable<Segment>, ISpatialKey
    {
        static Segment empty = new Segment(Coord.Empty, Coord.Empty);

        public static Segment Empty
        {
            get { return empty; }
        }

        Coord p;
        Coord q;

        public Segment(Coord p, Coord q)
        {
            this.p = p;
            this.q = q;
        }

        public Coord P
        {
            get { return p; }
        }

        public Coord Q
        {
            get { return q; }
        }

        public Extent Extent
        {
            get { return new Extent(p, q); }
        }

        public double SquareLength
        {
            get
            {
                double dx = q.X - p.X;
                double dy = q.Y - p.Y;

                return dx * dx + dy * dy;
            }
        }

        public bool IsEmpty
        {
            get { return p.IsEmpty || q.IsEmpty; }
        }

        public bool IsDegenerate
        {
            get { return p == q; }
        }

        public double Determinant
        {
            get { return p.X * q.Y - q.X * p.Y; }
        }

        /// <summary>
        /// calculate the sign of the determinant
        /// i.e. x1*y2 - y1*x2
        /// </summary>
        public int DeterminantSign
        {
            get
            {
                double x1 = p.X;
                double y1 = p.Y;
                double x2 = q.X;
                double y2 = q.Y;

                double u, v;

                // straight forward calculation
                u = x1 * y2;
                v = x2 * y1;
                if (u > v) return 1;
                if (u < v) return -1;
#if ROBUST
                
                #region DeterminantSign Original copyright

                //*************************************************************************
                //              2D and 3D determinant sign computation                     
                //*************************************************************************

                //*************************************************************************
                // ABDPY.h
                //*************************************************************************

                //*************************************************************************
                // Author : Olivier Devillers                                              
                // Olivier.Devillers@sophia.inria.fr                                       
                // http:/www.inria.fr:/prisme/personnel/devillers/anglais/determinant.html
                //*************************************************************************

                //*************************************************************************
                //              Copyright (c) 1995  by  INRIA Prisme Project               
                //                  BP 93 06902 Sophia Antipolis Cedex, France.            
                //                           All rights reserved                           
                //*************************************************************************

                //*************************************************************************
                // This code implement ideas presented in references given below
                // 
                // The given procedures compute the exact sign of a 2x2 or 3x3 determinant
                // whose entries are 52 bits integers in 2d case or 50 bits integers in
                // 3x3 case. The entries must be stored in variables of type "double".
                // 
                // The code use some feature of IEEE standard 754 arithmetic
                // 
                // 
                // 
                // REFERENCES :
                // 
                // @techreport{abdpy-esdus-94
                // , author =      "F. Avnaim and J.-D. Boissonnat and O. Devillers and F. Preparata and M. Yvinec"
                // , title =       "Evaluating signs of determinants using single-precision arithmetic"
                // , type =        "Research {Report}"
                // , number =      2306
                // , institution = "INRIA"
                // , address =     "BP93, 06902 Sophia-Antipolis, France"
                // , year =        1994
                // , url = "wais:/zenon.inria.fr:210/ra-mime-zenon-inria-fr?RR2306"
                // , abstract =    "We propose a method to evaluate signs of  $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous applications in geometric computation and provides a general and practical approach to robustness.  The algorithm has been implemented and experimental results show that it slows down the computing time by only a small factor  with respect to floating-point calculation."
                // }
                // 
                // @inproceedings{bddp-spsr-92
                // , author =      "F. Avnaim and J.-D. Boissonnat and O. Devillers and F. Preparata and M. Yvinec"
                // , title =       "Evaluating signs of determinants using single-precision arithmetic"
                // , booktitle =   "Proc. 11th Annu. ACM Sympos. Comput. Geom."
                // , year =        1995
                // , pages =       ""
                // }
                // 
                //*************************************************************************/

                #endregion

                // original source from http://www-sop.inria.fr/prisme/logiciel/determinant.html

                // modifications for zero equivalency added to ensure that values are within
                // some epsilon of zero

                int sign;
                double swap;
                double k; // quotient
                sign = 1;

                // testing null entries
                if ((x1.IsZero()) || (y2.IsZero())) // det = -x2 y1
                    if ((y1.IsZero()) || (x2.IsZero())) // det = 0.0
                        return 0;
                    else if (y1 > 0)
                        if (x2 > 0)
                            return -sign;
                        else
                            return sign;
                    else
                        if (x2 > 0)
                            return sign;
                        else
                            return -sign;
                if ((y1.IsZero()) || (x2.IsZero())) // det =  x1 y2
                    if (y2 > 0)
                        if (x1 > 0)
                            return sign;
                        else
                            return -sign;
                    else
                        if (x1 > 0)
                            return -sign;
                        else
                            return sign;

                // making y coordinates positive and permuting the entries
                // so that y2 is the biggest one
                {
                    if (0.0 < y1)
                    {   /* 0.0 < y1*/
                        if (0.0 < y2)
                        {   /* 0.0 < y1, y2*/
                            if (y1 <= y2)
                            {   /* 0.0 < y1 <= y2*/
                                /* everything ok*/
                            }
                            else
                            {   /* 0.0 < y2 < y1*/
                                /* permuting U1 U2*/
                                sign = -sign;
                                swap = x1; x1 = x2; x2 = swap;
                                swap = y1; y1 = y2; y2 = swap;
                            }
                        }
                        else
                        {   /* y2 < 0.0 < y1*/
                            if (y1 <= -y2)
                            {   /* 0.0 < y1 <= -y2*/
                                /* changing U2 sign*/
                                sign = -sign;
                                x2 = -x2; y2 = -y2;
                            }
                            else
                            {   /* 0.0 < -y2 < y1*/
                                /* changing U2 sign and permuting U1 U2*/
                                swap = x1; x1 = -x2; x2 = swap;
                                swap = y1; y1 = -y2; y2 = swap;
                            }
                        }
                    }
                    else
                    {   /* 0.0 < -y1*/
                        if (0.0 < y2)
                        {   /* 0.0 < -y1, y2*/
                            if (-y1 <= y2)
                            {   /* 0.0 < -y1 <= y2*/
                                /* changing U1 sign*/
                                sign = -sign;
                                x1 = -x1; y1 = -y1;
                            }
                            else
                            {   /* 0.0 < y2 < -y1*/
                                /* changing U1 sign and permuting U1 U2*/
                                swap = -x1; x1 = x2; x2 = swap;
                                swap = -y1; y1 = y2; y2 = swap;
                            }
                        }
                        else
                        {   /* y2 < 0.0 < -y1*/
                            if (y1 >= y2)
                            {   /* 0.0 < -y1 <= -y2*/
                                /* changing U1 U2 sign*/
                                x1 = -x1; y1 = -y1;
                                x2 = -x2; y2 = -y2;
                                ;
                            }
                            else
                            {   /* 0.0 < -y2 < -y1*/
                                /* changing U1 U2 sign and permuting U1 U2*/
                                sign = -sign;
                                swap = -x1; x1 = -x2; x2 = swap;
                                swap = -y1; y1 = -y2; y2 = swap;
                            }
                        }
                    }
                    /* making x coordinates positive*/
                    /* if |x2| < |x1| one can conclude*/
                    if (0.0 < x1)
                    {   /* 0.0 < x1*/
                        if (0.0 < x2)
                        {   /* 0.0 < x1, x2*/
                            if (x1 <= x2)
                            {   /* 0.0 < x1 < x2*/
                                /* everything ok*/
                            }
                            else
                            {   /* 0.0 < x2 < x1*/
                                return sign;
                            }
                        }
                        else
                        {   /* 0.0 < x1, -x2*/
                            return sign;
                        }
                    }
                    else
                    {   /* 0.0 < -x1*/
                        if (0.0 < x2)
                        {   /* 0.0 < -x1, x2*/
                            return -sign;
                        }
                        else
                        {   /* x2 < 0.0 < -x1*/
                            if (x1 >= x2)
                            {   /* 0.0 < -x1 <= -x2*/
                                /* changing x1 x2 sign*/
                                sign = -sign;
                                x1 = -x1; x2 = -x2;
                            }
                            else
                            {   /* 0.0 < -x2 < -x1*/
                                return -sign;
                            }
                        }
                    }
                }
                /* all entries strictly positive   x1 <= x2 and y1 <= y2*/
                while (true)
                {
                    k = Math.Floor(x2 / x1); x2 -= k * x1; y2 -= k * y1;
                    /* testing if R (new U2) is in U1 rectangle*/
                    if (y2 < 0.0) return -sign;
                    if (y2 > y1) return sign;
                    /* finding R'*/
                    if (x1 > x2 + x2)  /* 0 is candidate*/
                        if (y1 < y2 + y2)
                            return sign;
                        else  /* R' = R-0*/
                        { }
                    else  /* u1 is candidate*/
                        if (y1 > y2 + y2)
                            return -sign;
                        else  /* R' = u1-R*/
                        { x2 = x1 - x2; y2 = y1 - y2; sign = -sign; }
                    if (y2.IsZero()) return (x2.IsZero()) ? 0 : -sign;
                    if (x2.IsZero()) return sign;
                    /* exchange 1 and 2 role.*/
                    k = Math.Floor(x1 / x2); x1 -= k * x2; y1 -= k * y2;
                    /* testing if R (new U1) is in U2 rectangle*/
                    if (y1 < 0.0) return sign;
                    if (y1 > y2) return -sign;
                    /* finding R'*/
                    if (x2 > x1 + x1)  /* 0 is candidate*/
                        if (y2 < y1 + y1)
                            return -sign;
                        else  /* R' = R-0*/
                        { }
                    else  /* u2 is candidate*/
                        if (y2 > y1 + y1)
                            return sign;
                        else  /* R' = u2-R*/
                        { x1 = x2 - x1; y1 = y2 - y1; sign = -sign; }
                    if (y1.IsZero()) return (x1.IsZero()) ? 0 : sign;
                    if (x1.IsZero()) return -sign;
                }

#else
                return 0;
#endif
            }
        }

        public int Orientation(Coord coord)
        {
            // travelling along p1->p2, turn counter clockwise to get to q return 1,
            // travelling along p1->p2, turn clockwise to get to q return -1,
            // p1, p2 and q are colinear return 0.

            return new Segment(
                new Coord(q.X - p.X, q.Y - p.Y),
                new Coord(coord.X - q.X, coord.Y - q.Y)
                )
                .DeterminantSign;
        }

        public bool Equals(Segment other)
        {
            return p == other.p && q == other.q;
        }

        public override bool Equals(object obj)
        {
            if (obj is Segment)
                return Equals((Segment)obj);

            return false;
        }

        public override int GetHashCode()
        {
            return new HashFunction().Hash(p).Hash(q).HashCode;
        }

        public bool Intersects(Extent extent)
        {
            if (IsEmpty)
                return false;

            double minx;
            double maxx;

            double miny;
            double maxy;

            #region Check bounding box

            if (P.X < Q.X)
            {
                minx = P.X;
                maxx = Q.X;
            }
            else
            {
                minx = Q.X;
                maxx = P.X;
            }

            if (minx >= extent.Max.X || maxx < extent.Min.X)
                return false;

            if (P.Y < Q.Y)
            {
                miny = P.Y;
                maxy = Q.Y;
            }
            else
            {
                miny = Q.Y;
                maxy = P.Y;
            }

            if (miny >= extent.Max.Y || maxy < extent.Min.Y)
                return false;

            #endregion

            double num = Q.Y - P.Y;
            double denom = Q.X - P.X;

            double b;

            if (Math.Abs(num) <= double.Epsilon)
            {
                // horizontal line - no x intercept
                b = Q.Y;

                if (b >= extent.Max.Y || b < extent.Min.Y)
                    return false;

                return true;
            }
            else if (Math.Abs(denom) <= double.Epsilon)
            {
                // vertical line - no y intercept
                b = Q.X;

                if (b >= extent.Max.X || b < extent.Min.X)
                    return false;

                return true;
            }
            else
            {
                double m = num / denom;

                b = Q.Y - Q.X * m;

                // y = mx + b
                // x = (y - b) / m

                double x;
                double y;

                // check x = min.X boundary
                y = m * extent.Min.X + b;
                if (y >= extent.Min.Y && y < extent.Max.Y)
                    return true;

                // check x = max.X boundary
                y = m * extent.Max.X + b;
                if (y >= extent.Min.Y && y < extent.Max.Y)
                    return true;

                // check y = min.Y boundary
                x = (extent.Min.Y - b) / m;
                if (x >= extent.Min.X && x < extent.Max.X)
                    return true;

                // check y = max.Y boundary
                x = (extent.Max.Y - b) / m;
                if (x >= extent.Min.X && x < extent.Max.X)
                    return true;

                return false;
            }
        }

        public static bool operator ==(Segment a, Segment b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(Segment a, Segment b)
        {
            return !a.Equals(b);
        }
    }
}
